<html>
<head><meta charset="utf-8"><title>recursive solver, how it works · wg-traits · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/index.html">wg-traits</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html">recursive solver, how it works</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="232267912"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232267912" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232267912">(Mar 29 2021 at 13:31)</a>:</h4>
<p>how familiar are you with the recursive solver in general, <span class="user-mention" data-user-id="116266">@Santiago Pastorino</span> ?</p>



<a name="232267979"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232267979" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232267979">(Mar 29 2021 at 13:32)</a>:</h4>
<p>I'm not familiar with the solver :)</p>



<a name="232268008"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232268008" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232268008">(Mar 29 2021 at 13:32)</a>:</h4>
<p>but I meant, I know how prolog works</p>



<a name="232268032"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232268032" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232268032">(Mar 29 2021 at 13:32)</a>:</h4>
<p>more or less, did some prolog some years ago</p>



<a name="232268057"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232268057" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232268057">(Mar 29 2021 at 13:32)</a>:</h4>
<p>anyway, unsure exactly what you're asking about it :)</p>



<a name="232268172"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232268172" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232268172">(Mar 29 2021 at 13:33)</a>:</h4>
<p>I meant the recursive solver in chalk</p>



<a name="232268271"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232268271" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232268271">(Mar 29 2021 at 13:34)</a>:</h4>
<p><a href="https://rust-lang.github.io/chalk/book/recursive.html">https://rust-lang.github.io/chalk/book/recursive.html</a></p>



<a name="232268339"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232268339" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232268339">(Mar 29 2021 at 13:34)</a>:</h4>
<p>while I work through this, we can break out a topic to talk about that if you like :)</p>



<a name="232268421"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232268421" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232268421">(Mar 29 2021 at 13:35)</a>:</h4>
<p>kind of useful background material :)</p>



<a name="232269406"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232269406" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232269406">(Mar 29 2021 at 13:41)</a>:</h4>
<p>I actually don't know how to explain it better than this chapter</p>



<a name="232269415"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232269415" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232269415">(Mar 29 2021 at 13:41)</a>:</h4>
<p>but I'm happy to answer questions</p>



<a name="232271213"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271213" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271213">(Mar 29 2021 at 13:52)</a>:</h4>
<p>it's clear to me :)</p>



<a name="232271302"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271302" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271302">(Mar 29 2021 at 13:52)</a>:</h4>
<p>I guess from what I'm reading and saw in some other discussions that chalk is or was migrating from a recursive solver to an SLG solver?</p>



<a name="232271382"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271382" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271382">(Mar 29 2021 at 13:53)</a>:</h4>
<p>I'd say the jury is still out</p>



<a name="232271405"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271405" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271405">(Mar 29 2021 at 13:53)</a>:</h4>
<p>the recursive solver has some real advantages i the short term</p>



<a name="232271434"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271434" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271434">(Mar 29 2021 at 13:53)</a>:</h4>
<p>something like the SLG solver may be useful in the longer term, though maybe even a fancier approach</p>



<a name="232271572"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271572" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271572">(Mar 29 2021 at 13:54)</a>:</h4>
<p>I guess SLG solver is Prolog solver</p>



<a name="232271643"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271643" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271643">(Mar 29 2021 at 13:54)</a>:</h4>
<p>anyway, I kind of informally have an idea how it works, but not 100% or neither know the corner cases and stuff like that :P</p>



<a name="232271748"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271748" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271748">(Mar 29 2021 at 13:55)</a>:</h4>
<p><span class="user-mention silent" data-user-id="116266">Santiago Pastorino</span> <a href="#narrow/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works/near/232271572">said</a>:</p>
<blockquote>
<p>I guess SLG solver is Prolog solver</p>
</blockquote>
<p>sort of</p>



<a name="232271759"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271759" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271759">(Mar 29 2021 at 13:55)</a>:</h4>
<p>prolog solver is kind of neither</p>



<a name="232271777"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271777" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271777">(Mar 29 2021 at 13:55)</a>:</h4>
<p>at least, a trad. prolog solver</p>



<a name="232271835"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271835" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271835">(Mar 29 2021 at 13:56)</a>:</h4>
<p>searching a bit ended at <a href="https://github.com/rust-lang/chalk/issues/59">chalk#59</a></p>



<a name="232271838"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271838" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271838">(Mar 29 2021 at 13:56)</a>:</h4>
<p>:)</p>



<a name="232271839"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271839" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271839">(Mar 29 2021 at 13:56)</a>:</h4>
<p>but the slg solver is like a more capable prolog solver</p>



<a name="232271892"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271892" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271892">(Mar 29 2021 at 13:56)</a>:</h4>
<p>that can handle inductive cycles</p>



<a name="232271906"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271906" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271906">(Mar 29 2021 at 13:56)</a>:</h4>
<p>and doesn't always solve depth first</p>



<a name="232271920"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271920" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271920">(Mar 29 2021 at 13:56)</a>:</h4>
<p>ok</p>



<a name="232271960"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232271960" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232271960">(Mar 29 2021 at 13:57)</a>:</h4>
<p>I also wrote some blog posts about this</p>



<a name="232272061"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232272061" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232272061">(Mar 29 2021 at 13:57)</a>:</h4>
<p>yeah also ended seeing <a href="https://smallcultfollowing.com/babysteps/blog/2017/10/21/chalk-meets-slg/">https://smallcultfollowing.com/babysteps/blog/2017/10/21/chalk-meets-slg/</a></p>



<a name="232273256"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/recursive%20solver%2C%20how%20it%20works/near/232273256" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Santiago Pastorino <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/recursive.20solver.2C.20how.20it.20works.html#232273256">(Mar 29 2021 at 14:05)</a>:</h4>
<p><span class="user-mention" data-user-id="116009">@nikomatsakis</span> didn't read that article, but may save it for later</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>